package number_351;


import java.util.Arrays;

/**
 * 我们都知道安卓有个手势解锁的界面，是一个 3 x 3 的点所绘制出来的网格。
 *
 * 给你两个整数，分别为 ​​m 和 n，其中 1 ≤ m ≤ n ≤ 9，那么请你统计一下有多少种解锁手势，是至少需要经过 m 个点，但是最多经过不超过 n 个点的。
 *
 *  
 *
 * 先来了解下什么是一个有效的安卓解锁手势:
 *
 * 每一个解锁手势必须至少经过 m 个点、最多经过 n 个点。
 * 解锁手势里不能设置经过重复的点。
 * 假如手势中有两个点是顺序经过的，那么这两个点的手势轨迹之间是绝对不能跨过任何未被经过的点。
 * 经过点的顺序不同则表示为不同的解锁手势。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/android-unlock-patterns
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Solution {
    private boolean[] isUsed = new boolean[9];
    public int numberOfPatterns(int m, int n) {
        int res = 0;
        for (int len = m; len <= n; len++) {
            res += calculatePatters(-1, len);
            Arrays.fill(isUsed, false);
        }
        return res;
    }

    private int calculatePatters(int last, int len) {
        if (len == 0) {
            return 1;
        }
        int sum = 0;
        for (int i = 0; i < 9; i++) {
            if (isValid(i, last)) {
                isUsed[i] = true;
                sum += calculatePatters(i, len - 1);
                isUsed[i] = false;
            }
        }
        return sum;
    }

    private boolean isValid(int index, int last) {
        if (isUsed[index]) {
            return false;
        }
        if (last == -1) {
            return true;
        }
        if ((index + last) % 2 == 1) {
            return true;
        }
        int mid = (index + last) / 2;
        if (mid == 4) {
            return isUsed[mid];
        }
        if ((index % 3 != last % 3) && (index / 3) != last / 3) {
            return true;
        }
        return isUsed[mid];
    }

    public static void main(String[] args) {
        new Solution().numberOfPatterns(2,2);
    }
}
